#pragma once

#include <functional>
#include <string>
#include <cmath>

using namespace std;
template<class K, class V>
struct Node
{
	Node<K, V>(){};
	Node<K, V>(K key, V value)
	{
		this->key = key, this->value = value;
	}
	K key;
	V value;
};

template<class K, class V>
struct Element
{
	Element<K, V>()
	{
		ptr = nullptr;
	}
	Element<K, V>(int capacity)
	{
		ptr = new Node<K, V>[capacity];
		this->capacity = capacity;
	}

	Node<K, V> *ptr;
	int capacity;
	int size;
};

template<class K, class V>
class HashTable
{
private:
	Element<K, V> **arr;
	int size;
	int capacity;
	hash<K> myHash;
public:

	HashTable()
	{
		this->size = 7;
		this->capacity = 2;
		arr = new Element<K, V>*[size];

		for (int i = 0; i < size; i++)
		{
			//arr[i] = new Element<K, V>(2);
			arr[i] = nullptr;
		}
	}
	HashTable(int size_hash_table, int size_bucket_array)
	{
		this->size = size_hash_table;
		this->capacity = size_bucket_array;
		arr = new Element<K, V>*[size];

		for (int i = 0; i < size; i++)
		{
			//arr[i] = new Element<K, V>(2);
			arr[i] = nullptr;
		}
	}

	~HashTable()
	{
		for (int i = 0; i < size; i++)
		{
			if (arr[i] != nullptr)
				delete[] arr[i];
		}
		delete[] arr;
	}

	int calc_hash(K key)
	{
		int hash_key = myHash(key);
		int place = abs(hash_key) % size;
		return place;
	}

	void Add(Node<K, V> *n)
	{
		int place = calc_hash(n->key);

		if (arr[place] == nullptr)
		{
			arr[place] = new Element<K, V>(capacity);
			arr[place]->ptr[0] = *n;
			arr[place]->size = 1;
		}
		else
		{
			if (arr[place]->size < arr[place]->capacity)
			{
				arr[place]->ptr[arr[place]->size] = *n;
				arr[place]->size++;
			}
			else
			{
				Element<K, V> *e = new Element<K, V>(arr[place]->capacity + 4);
				Element<K, V> *d;
				for (int i = 0; i < arr[place]->size; i++)
				{
					e->ptr[i].key = arr[place]->ptr[i].key;
					e->ptr[i].value = arr[place]->ptr[i].value;
				}
				e->size = arr[place]->size;

				d = arr[place];
				arr[place] = e;
				arr[place]->ptr[arr[place]->size] = *n;
				arr[place]->size++;
				delete[] d;
			}
		}
	}

	void Print()
	{
		for (int i = 0; i < size; i++)
		{
			if (arr[i] != nullptr)
			{
				cout << i << endl;
				for (int j = 0; j < arr[i]->size; j++)
					cout << "  " << arr[i]->ptr[j].key << " : " << arr[i]->ptr[j].value << endl;
			}
		}
	}

	Node<K, V> *search(K key)
	{
		int place = calc_hash(key);

		if (arr[place] != nullptr)
		{
			for (int i = 0; i < arr[place]->size; i++)
			{
				if (arr[place]->ptr[i].key == key)
					return &arr[place]->ptr[i];
			}
			return nullptr;
		}
		else
			return nullptr;
	}
};

